目標 🎯
- 課題： ソースサーバー `S` からすべての他のサーバーへの最適な経路を見つける。
- 出力内容： 各サーバー `i` について、以下の値を計算する必要がある：
- 総レイテンシ： `S` から `i` までの最小コスト（最短経路）
- 次のホップ： その最短経路上の最初のサーバー
- 例： `S` から `D` への最良経路が `S -> A -> B -> D` の場合、**次のホップ**は `A` となる。
ネットワーク 💾
次のデータ構造を使用する：隣接リスト を用いてネットワークを表現する。
- サーバーはノードである。
- 接続は双方向エッジである。
- レイテンシは正の重みである。
// 接続：0-1 (10ms), 0-2 (3ms)
adj = [
0:[(1, 10), (2, 3)],
1:[(0, 10)],
2:[(0, 3)],
...
]
adj = [
0:[(1, 10), (2, 3)],
1:[(0, 10)],
2:[(0, 3)],
...
]
出力形式 ⚙️
`V` 行を出力する必要がある。各行 `i` はサーバー `i` に対応する。
[レイテンシ] [次のホップ]到達可能なノードの場合。
0 -1ノードがソース `S` そのものの場合。
-1 -1ノードが `S` から到達不可能な場合。